#include <iostream>
#include <bits/stdc++.h>
using namespace std;

class Sort
{
public:
	void mergesort(vector<int>& _nums)
	{
		vector<int> nums = _nums;
		_mergesort(nums, 0, nums.size() - 1);
		print(nums);
	}
	void quicksort(vector<int>& _nums)
	{
		vector<int> nums = _nums;
		_quicksort(nums, 0, nums.size() - 1);
		print(nums);
	}
	void bubblesort(vector<int>& _nums)
	{

	}
private:
	void print(vector<int>& nums)
	{
		for (auto e : nums)
			cout << e << " ";
		cout << endl;
	}
	void _mergesort(vector<int>& nums, int left, int right)
	{
		if (left >= right)
			return;
		int midi = left + (right - left) / 2;
		_mergesort(nums, left, midi);
		_mergesort(nums, midi + 1, right);

		vector<int> tmp(nums.size());
		int cur1 = left, cur2 = midi + 1, i = 0;
		while (cur1 <= midi && cur2 <= right)
		{
			if (nums[cur1] < nums[cur2])
				tmp[i++] = nums[cur1++];
			else
				tmp[i++] = nums[cur2++];
		}
		while (cur1 <= midi)
			tmp[i++] = nums[cur1++];
		while (cur2 <= right)
			tmp[i++] = nums[cur2++];
		for (int j = left; j <= right; j++)
			nums[j] = tmp[j - left];
	}
	void _quicksort(vector<int>& nums, int l, int r)
	{
		if (l >= r)
			return;
		//int key = getrandom(nums, l, r);
		int key = nums[l];
		int left = l - 1, right = r + 1, i = l;
		while (i < right)
		{
			if (nums[i] < key)
				swap(nums[++left], nums[i++]);
			else if (nums[i] > key)
				swap(nums[--right], nums[i]);
			else
				i++;
		}
		_quicksort(nums, l, left);
		_quicksort(nums, right, r);
	}
	int getrandom(vector<int>& nums, int left, int right)
	{
		return nums[rand() % (right - left + 1) + left];
	}
};

int main()
{
	vector<int> nums{ 1,4,5,7,9,8,2,2,111 };
	Sort().quicksort(nums);
	//Sort().mergesort(nums);
	return 0;
}